#include <bits/stdc++.h>
using namespace std;
const int MOD=9973;
struct Mat{
    int m[12][12];

    Mat operator *(const Mat& rhs){
        Mat t;
        memset(t.m,0,sizeof(t.m));
        for(int k=0;k<12;k++){
            for(int i=0;i<12;i++){
                if(m[i][k]==0){
                    continue;
                }
                for(int j=0;j<12;j++){
                    if(rhs.m[k][j]==0){
                        continue;
                    }
                    t.m[i][j]=(t.m[i][j]+(m[i][k]%MOD*rhs.m[k][j]%MOD)%MOD)%MOD;
                }
            }
        }
        return t;
    }

    Mat operator ^(int n){
        Mat ans;
        memset(ans.m,0,sizeof(ans.m));
        for(int i=0;i<12;i++){
            ans.m[i][i]=1;
        }
        while(n){
            if(n%2){
                ans=ans*(*this);
            }
            n/=2;
            (*this)=(*this)*(*this);
        }
        return ans;
    }
};
int main(void){
    int t,n,k;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&k);
        Mat t;
        memset(t.m,0,sizeof(t.m));
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                scanf("%d",&t.m[i][j]);
            }
        }
        Mat g=t^k;
        // for(int i=0;i<n;i++){
        //     for(int j=0;j<n;j++){
        //         printf("%d ",g.m[i][j]);
        //     }
        //     printf("\n");
        // }
        int ans=0;
        for(int i=0;i<n;i++){
            ans=(ans+g.m[i][i])%MOD;
        }
        printf("%d\n",ans);
    }
    return 0;
}